import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.ArrayList;
import java.util.Stack;

public class Tunnel {

	/**
	 * @param args
	 */
	protected int f[][];
	protected int c[][];
	protected int number;
	protected Vertex Svertex;
	protected Vertex Evertex;
	public static void main(String[] args) {
		long startTime,endTime,longTime;
		
		int n = 0;
		int m = 0;
		int stpoint = 0;
		int expoint = 0;
		int maxFlow=0;
		int[] shortest;
		Maze mb = null;
		ArrayList<Vertex> vt = new ArrayList<Vertex>();
		Stack<Integer> arrange2 = new Stack<Integer>();
		Stack<Integer> arrange3 = new Stack<Integer>();
		
		startTime=System.currentTimeMillis();
		try {
			FileReader fr = new FileReader("maze_test3.txt");
			BufferedReader input = new BufferedReader(fr);
			String temp;
			while ((temp = input.readLine()) != null) {
				n = Integer.parseInt(temp);
				m = Integer.parseInt(input.readLine());
				Maze ma = new Maze(n, m);
				for (int i = 0; i < n; i++) {
					char[] str = input.readLine().trim().toCharArray();
					System.out.println(str);
					ma.mat[i] = str;
				}
				stpoint = Integer.parseInt(input.readLine());
				expoint = Integer.parseInt(input.readLine());
				mb = ma;
			}
			input.close();
		} catch (Exception e) {
			System.err.println("Error: " + e.getMessage());
		}
		System.out.println("Number of rows n = " + n
				+ "\nNumber of columns m =: " + m);
		System.out.println("Station point: " + stpoint + "(" + stpoint / m
				+ "," + stpoint % m + ")" + "\nExit point: " + expoint + "("
				+ expoint / m + "," + expoint % m + ")");

		Tunnel tunel= new Tunnel();
		tunel.Svertex = new Vertex(mb, stpoint);
		tunel.Evertex = new Vertex(mb, expoint);
		System.out.println("start" + tunel.Svertex.value + "(" + tunel.Svertex.x + ","
				+ tunel.Svertex.y + ")");
		System.out.println("end" + tunel.Evertex.value + "(" + tunel.Evertex.x + ","
				+ tunel.Evertex.y + ")");

		Graph g = new Graph(mb);

		for (int i = 1; i < g.get_n() - 1; i++) { // Browsing the matrix without
													// its border
			for (int j = 1; j < g.get_m() - 1; j++) {
				if (g.isVertex(i, j)) {
					vt.add(new Vertex(mb, ((i - 1) * (g.get_m() - 2) + (j - 1))));
					// System.out.println((i - 1) * (g.get_m() - 2) + (j - 1) +
					// "(" + (i - 1) + "," + (j - 1) + ")");
				}
			}
		}
		g.dismat = new int[vt.size()][vt.size()];
		/*
		 * Initialize value of Distance matrix = -1 by default and the value of
		 * main diagonal = 0
		 */
		for (int i = 0; i < vt.size(); i++) {
			for (int j = 0; j < vt.size(); j++) {
				g.dismat[i][j] = -1;
				g.dismat[i][i] = 0;
			}
		}
		System.out
				.println("Number of vertex is founded by 1st solution equal:  "
						+ vt.size());
		for (Vertex v : vt)
			System.out.println(v.value + "(" + v.x + "," + v.y + ")");
		g.vertices.add(vt.get(0));
		g.move2(g.vertices.get(0));
		System.out
				.println("Number of vertex is founded by 2nd solution equal: "
						+ g.vertices.size());
		for (Vertex v : g.vertices)
			System.out.println(v.value + "(" + v.x + "," + v.y + ")");
		System.out.println();
		System.out.println("Distance matrix:");
		System.out.println(g);
		writeFile("diagram.txt", genDiagram(g));
		// ----------------------sentence b-----------------------------------
		
		
		Floyd d = new Floyd();	
		if(d.shortesPath(g, tunel.Svertex, tunel.Evertex)){
		arrange2=d.arrange;		
		String str = "";
		int sum = 0;
		while (!arrange2.isEmpty()) {
			int i, j;
			i = arrange2.pop();
			j = arrange2.peek();
			str += g.vertices.get(i-1).value + "-";
			sum += g.dismat[i-1][j-1];
			if (arrange2.size() == 1) {
				str += g.vertices.get(arrange2.pop()-1).value + "\n";
			}
			
		}
		System.out.println("Content is: "+str + sum);
		writeFile("shortest_path.txt", str + sum);
		}
		else{
			System.out.println("Not path from start to end ");
		}
		endTime=System.currentTimeMillis();
		longTime=(endTime-startTime);
		System.out.println("time"+longTime +"miliseconds");
	// ----------------------------------sentence c--------------------------
		
//		FordFulkeson ff= new FordFulkeson( );
//		System.out.println("Ford");
//		int t=0;
//		Tunnel tunel= new Tunnel();
//		tunel.initialFord(g);
//		int temp=0;
//		while(temp<2){
//		if(d.shortesPath(g, Svertex, Evertex)==true){
//			
//			arrange3=d.arrange;
//			System.out.println(arrange3.size());
//			shortest= new int[arrange3.size()];
//			int i=0;
//			// copy stack into array 
//			while(!arrange3.isEmpty()){
//				shortest[i]=arrange3.pop();
//			//	System.out.print(shortest[i]);
//				i++;
//			}
//			maxFlow+=ff.minPath1(shortest,tunel.c,tunel.h,tunel.f,g.vertices.size());
//			int[][] temp1 = new int[g.vertices.size()][g.vertices.size()];
//			temp1=ff.c;
//			System.out.println("Max"+maxFlow);
//			for (int x = 0; x < g.vertices.size(); x++) {
//				for (int y = 0; y < g.vertices.size(); y++) {
//						System.out.print(temp1[x][y]);
//						System.out.print("\t");
//											
//				}	
//				System.out.print("\n");
//			}
//		}
//		temp ++;
//		System.out.println("Max"+maxFlow);
//		}
	}
	public  void initialFord(Graph g)
	{		
		int n= g.vertices.size();
		c= new int[n][n];

		f= new int[n][n];
		//inital capacity matrix and flow matrix
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
					c[i][j]=g.dismat[i][j];
					f[i][j]=0;
				
					if(c[i][j]==-1){
						c[i][j]=10000;
					}				
			}			
		}
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				if(c[i][j]>0 && c[j][i]>0)
				{
					c[j][i]=0;
				}
			}
		}
		
		
	}
	public static String genDiagram(Graph g) {
		String content = "";
		for (int i = 0; i < g.vertices.size(); i++) {
			content += g.vertices.get(i).value;
			for (int j = 0; j < g.vertices.size(); j++) {
				if (g.dismat[i][j] > 0) {
					content +=" (" + g.vertices.get(j).value + ","
							+ g.dismat[i][j] + ")";
				}
			}
			content += "\n";
		}
		return content;
	}
	
	public static void writeFile(String name, String content){
		try {
			File file = new File(name);
			if (!file.exists()) {
				file.createNewFile();
			}
			FileWriter fw = new FileWriter(file);
			BufferedWriter bw = new BufferedWriter(fw);
			bw.write(content);
			bw.close();

		} catch (Exception e) {
			System.err.println("Error: " + e.getMessage());
		}
	}
}
